# 在一个数组中，求连续的子数组，和为 target，的子数组个数。

# 1. 设计：使用双指针，不定长滑动窗口: 
arr = [1, -9, 5, 3, 4, 4]

def getTargetSum(nums, target):
    """
        有 bug！！！， 只适用于正数的情况！！
    """
    n = len(nums)
    total = 0
    cnt = 0
    i = 0
    for j in range(n):
        total += nums[j]
        if total == target:
            cnt += 1
        elif total < target:
            continue
        else:
            while total >= target: 
                total -= nums[i]
                i += 1
                if total == target:
                    cnt += 1

    return cnt


# 代码优化if else
def getTargetSum(nums, target):
    n = len(nums)
    total = cnt = i = 0
    for j in range(n):
        total += nums[j]
        while total > target: 
            total -= nums[i]
            i += 1
        if total == target:
            cnt += 1
    
    return cnt


# 2. 使用前缀和， 适用于正负数的情况
def getTargetSum(nums, target):
    """
        计算前缀和(prefix)的同时， 进行判断，当前是否已经出现了 和为 target的片段
        这里nums中 i 到 j 的片段 和为  prefix[j + 1] - prefix[i] == target
        变换一下： prefix[j + 1] - target == prefix[i] ，只需要找，是否存在对应的 prefix[i]即可
    """
    n = len(nums)
    map = dict()
    prefix = [0] * (n + 1)
    cnt = 0
    for j in range(n):
        prefix[j + 1] = prefix[j] + nums[j]
        # if prefix[j + 1] - target in map:
        #     cnt += map.get(prefix[j + 1] - target)
        # 优化 if 写法
        cnt += map.get(prefix[j + 1] - target, 0)

        map[prefix[j + 1]] = map.get(prefix[j + 1], 0) + 1
    
    return cnt



rst = getTargetSum(arr, 8)
print(rst)

